package com.openess.bigsearch.engine.utils.sort;

import java.util.Comparator;

public class HeapSort<E> implements Sort<E> {
	/**
	 * 堆的大小，即已建立好最大堆的子树的元素个数
	 */
	protected int count = 0;

	/**
	 * 左孩子
	 * 
	 * @param i
	 * @return
	 */
	private int left(int i) {
		return 2 * (i + 1) - 1;
	}

	/**
	 * 右孩子
	 * 
	 * @param i
	 * @return
	 */
	private int right(int i) {
		return 2 * (i + 1);
	}

	/**
	 * 拿到父母的位置
	 * 
	 * @param i
	 * @return
	 */
	protected int parent(int i) {
		return (i - 1) / 2;
	}

	/**
	 * 堆的大小，不等于数组的大小
	 * 
	 * @return
	 */
	protected int heapSize() {
		return count;
	}

	/**
	 * 数组中所有元素的个数
	 * 
	 * @param arrays
	 * @return
	 */
	public int length(E[] arrays) {
		return arrays.length;
	}

	/**
	 * 以指定的位置作为根，构建子树的最大堆。前提：以i为根的树，其左右孩子树已经是最大堆
	 * 
	 * @param arrays
	 *            准备构建最大堆的数组
	 * @param i
	 *            以数组中第i个元素作为根，构建最大堆
	 */
	private void maxHeapify(E[] arrays, int i, Comparator<? super E> c) {
		int largest;
		int l = left(i);
		int r = right(i);
		// 如果左孩子节点不在堆内，那右孩子节点无需判断即可知必然不会在堆内。
		// 如果l>heapSize()，说明i是树中的叶子节点，叶子不需要建堆
		while (l < heapSize()) {
			if (c.compare(arrays[l], arrays[i]) > 0)
				largest = l;
			else
				largest = i;
			if (r < heapSize() && c.compare(arrays[r], arrays[largest]) > 0)
				largest = r;
			if (largest != i) {
				E temp = arrays[i];
				arrays[i] = arrays[largest];
				arrays[largest] = temp;
				l = left(largest);
				r = right(largest);
				i = largest;
			} else {
				l = heapSize();
			}
		}
	}

	/**
	 * 对整个数组，进行循环建堆
	 * 
	 * @param arrays
	 */
	private void buildMaxHeap(E[] arrays, Comparator<? super E> c) {
		this.count = length(arrays);
		// 叶子节点没有孩子，不需要建堆，直接从最后一个内节点开始建堆，一直建到整棵树的根节点，即数组的第一个
		for (int i = length(arrays) / 2 - 1; i >= 0; i--) {
			maxHeapify(arrays, i, c);
		}
	}

	/**
	 * 进行排序
	 * 
	 * @param arrays
	 * @return
	 */
	public void sort(E[] arrays, int p, int r, Comparator<? super E> c) {
		// 先把整个数组建成最大堆
		buildMaxHeap(arrays, c);
		// 再把数组中的第一个值(最大值)和最后一个值进行交换，在排除最后一个数组位置的情况下，再建堆。
		// 依次循环，直到堆中只剩一个节点(即节点没有孩子)
		for (int i = length(arrays) - 1; i >= 1; i--) {
			E temp = arrays[0];
			arrays[0] = arrays[i];
			arrays[i] = temp;
			this.count--;
			maxHeapify(arrays, 0, c);
		}
	}

	/**
	 * 计算数组中的最大值，利用堆排序比其他排序方法效率要高，因为不需要为整个数组排序，因此一次调用buildMaxHeap即可，时间复杂度：O(n).
	 * 
	 * @param arrays
	 * @return
	 */
	public E max(E[] arrays, Comparator<? super E> c) {
		buildMaxHeap(arrays, c);
		return arrays[0];
	}
}
